The libart library
<<< Previous Page	Home		Next Page >>>

Libart Internals

Table of Contents
Rasterizer
Intersector

Rasterizer

The rasterizer code we will refer to is the function named art_svp_render_aa located in the file art_svp_render_aa.c.

Winding Number Calculation.

The goal of the libart rasterizer is to calculate a property for each of the pixels to render: this is the winding number. This property reflects the position of a given pixel relative to all the vector paths to render. It says whether or not the pixel is located inside or outside a vector path. As can be seen on the folowing diagram, a point is inside a given closed polygon if and only if the infinite horizontal half-line starting on the pixel and going to the left intersects the enclosing polygon an odd number of times.

Figure 1. Inside or Outside of a polygon

The winding number of a pixel is defined as the number of times the horizontal line intersects an up segment minus the number of times the horizontal line intersects down segments (a segment being defined by a pair of points A=(Ax, Ay) and B=(Bx, By), an up segment is a segment such that By > Ay). A non-zero winding number thus means the pixel is located within a polygon and must be painted.

Classicaly, the winding number property is calculated on each pixel and this information is used to paint a pixel in either black or white (this is what the standard freetype renderer used to do to render each character on screen). The problem here is that the output medium used by computers does not have an infinite spatial resolution. Computer screens (CRTs or LCDs or even printers) draw dots with a non-zero area. Each of the displayed pixel is not a point in the mathematical sense. Traditionaly, to render the vector paths, we would test whether or not the center of each pixel lies within the vector path: this rendering method introduces a number of well known artificial artefacts which are usually refered to as aliasing artefacts.

Hopefully, there exist antialiasing techniques to minimize these aliasing artifacts. The idea behind all these techniques is to fake higher resolution on the output medium by trading-off color depth for spatial resolution: certain pixels are not completely turned black (they are turned grey) to give viewers the feeling of smooth outines rather than jagged outlines.

Figure 2. Oversampling versus Exact Coverage Calculus

Traditional antialiasing algorithms use Oversampling: they render the outlines on a high-resolution grid and then calculate the grey output by averaging over the high-resolution B&W grid. Libart instead tries to calculate the real coverage of each pixel by the outline to get better precision than with oversampling.

To express this new concept (that is, partial coverage of a pixel rather than Black or White), libart redefines winding numbers and uses a special data structure which is of importance to describe them: ArtSVPRenderAAStep.

To understand how they are used, we'll use the example shown in the figure below. On the bottom row of pixels, pixel 3 would be represented by the step (x=1, delta=+0.3), pixel 4 by the step (x=2, delta=+0.67) and pixels 5 and 6 by the step (x=3, delta=+0.03).

The bottom row of pixels is rendered as folows: we begin by rendering the first step which says that pixel 1 on this row is 30% covered by the outline (delta=0.3 -> 30%). The second step tells us that the second pixel on this row is (30+67)=97% covered by the outline (the difference -the delta- is of +0.67). Finally, the third step tells us that pixels 3 and folowing on this row are (97+3)=100% covered by the outline. The fourth step would tell us where the pixels are not 100% covered anymore. To summarize, on a given row of pixels, each step gives us the delta (that is, the difference in coverage) relative to the previous step of the current pixel.

The raster version of an outline can thus be represented relative to an output buffer by an array of arrays of ArtSVPRenderAASteps. Each array of ArtSVPRenderAASteps represents a row of pixels of the output buffer and each step of the array of ArtSVPRenderAASteps represents a run (that is, adjacent pixels with same color characteristics).

People who want to render the real pixels in the output buffer just need to calculate running sums over the steps for each line of the output buffer. The running sum represents the degree of presence of the outline over the background: the outline is easy to composite over the backgound.

How libart does this for true.

art_svp_render_aa exports the API which offers the interface described in the previous section: a callback is called on each of the output buffer's line with an array of ArtSVPRenderAASteps as parameter. This callback just needs to calculate the running sum for this line and render the real pixels in a pixel buffer.

art_rgb_svp_aa and art_rgb_svp_alpha both use internally art_svp_render_aa by providing different callbacks. Their code is pretty simple and can be found in art_rgb_svp.c (the code for their associated callbacks can be found in the same file).

The interesting piece of code is indeed art_rgb_svp_aa. This code implements a pretty classic Plane Sweep algorithm: it loops over the output buffer's lines and calculates for each line the steps for the callback. To calculate the steps, it maintains over the lines the list of segments crossing the current line.

A Plane Sweep Algorithm

To maintain the list of active segments (that is, segments crossing the current line), the algorithm adds the segments starting on the current line and removes the segments ending on the current line. The folowing pseudo-code summarizes this process for libart's (x,y) space.

for (y = 0; y < height; y++) {
	add_new_active_segments (active_segments, svp);
	
	process_line (active_segments, y);

	remove_old_active_segments (active_segmnts);
}

Surprisingly enough, the svp data-structure was designed so that the two important operations of this algorithm (namely, adding new active segments and removing old active segments to/from the list of active segments) are easy to implement and fast.

Let's first have a look at what the SVP data structure looks like.

typedef struct _ArtSVP ArtSVP;
typedef struct _ArtSVPSeg ArtSVPSeg;

struct _ArtSVPSeg {
  int n_points;
  int dir; /* == 0 for "up", 1 for "down" */
  ArtDRect bbox;
  ArtPoint *points;
};

struct _ArtSVP {
  int n_segs;
  ArtSVPSeg segs[1];
};

Each of an SVP's segment represent a monotonous vector shape as shown on the figure below. The word Monotonous used here is to be understood as not changing vertical direction: segments either go up or down. A given Vector path changing his vertical direction is split in two vector paths when represented by an SVP: one going up and one going down. Each segment is contained within its own bounding box stored in the bbox field.

Figure 3. VPath to SVP

The segments listed in an SVP are ordered using their starting points as shown in art_svp_seg_compare (from art_svp.c) from top to bottom, left to right. The ordering of the segments and their bounding boxes allows one to easily parse the list of segments of an svp to update the list of active segments:

  for (y = y0; y < y1; y++)
    {
      /* insert new active segments */
      for (; i < svp->n_segs && svp->segs[i].bbox.y0 < y + 1; i++)
	{
	  if (svp->segs[i].bbox.y1 > y &&
	      svp->segs[i].bbox.x0 < x1)
	    {
	      seg = &svp->segs[i];
	      /* move cursor to topmost vector which overlaps [y,y+1) */
	      for (curs = 0; seg->points[curs + 1].y < y; curs++);
	      cursor[i] = curs;
	      dy = seg->points[curs + 1].y - seg->points[curs].y;
	      if (fabs (dy) >= EPSILON)
		seg_dx[i] = (seg->points[curs + 1].x - seg->points[curs].x) /
		  dy;
	      else
		seg_dx[i] = 1e12;
	      seg_x[i] = seg->points[curs].x +
		(y - seg->points[curs].y) * seg_dx[i];
	      art_svp_render_insert_active (i, active_segs, n_active_segs++,
					    seg_x, seg_dx);
	    }
	}


	  /* here, process the current list of active segments.*/


	/* remove old segments from active list */
	if (seg->points[curs].y >= y + 1)
	  {
	    curs--;
	    cursor[seg_index] = curs;
	    seg_x[seg_index] += seg_dx[seg_index];
	  }
	else
	  {
	    art_svp_render_delete_active (active_segs, j--,
					    --n_active_segs);
	  }
    }

A note on coverage calculus in art_svp_render_aa

Because the code which calculates the different steps for each line of the output buffer is not that easy to get right quickly, here is included a simple diagram which outlines the meaning of the variables of the code:

Figure 4. Coverage Calculus